定义类型的模块

  基于模块的程序设计趋向于以一个类型的所有数据为中心，在某个类型管理模块的控制之下工作。例如，如果我们希望有许多堆栈---而不是像前面那样只用一个由 Stack 模块提供的堆栈---我们就可能会定义一个堆栈管理器，它具有如下的界面：

    namespace Stack
    {
        struct Rep;                // 在另外某个地方定义堆栈的布局
        typedef Rep& stack;

        stack create();            // 做出一个新堆栈
        void destroy(stack s);     // 删除s

        void push(stack s, char c);// 将c压入s
        char pop(stack s);         // 弹出s
    }

声明

    struct Rep;

说 Rep 是一个类型的名字，但将这个类型留待以后再去定义。声明

    typedef Rep& stack;

确定名字 stack 是“对Rep的引用”。这里的想法是，堆栈由 Stack::stack 表示，而进一步的细节则对用户隐藏起来。

一个 Stack::stack 用起来很像一个内部类型的变量：

    struct Bad_pop { };

    void f()
    {
        Stack::stack s1 = Stack::create();    // 做出一个新堆栈
        Stack::stack s2 = Stack::create();    // 做出另一个新堆栈

        Stack::push(s1, 'c');
        Stack::push(s2, 'k');

        if(Stack::pop(s1) != 'c') throw Bad_pop();
        if(Stack::pop(s2) != 'k') throw Bad_pop();

        Stack::destroy(s1);
        Stack::destroy(s2);
    }

我们可以以几种不同的方式来实现这个堆栈。最重要的是，用户完全不必知道我们到底是怎么做的。只要我们能保持这个界面不改变，即使是决定重新实现 Stack，用户也不会受到任何影响。

某个实现可以是预先分配几个堆栈，而让 Stack::create() 递交出到某个尚未使用的堆栈的引用。而 Stack::destroy() 则将一个堆栈表示标记为未使用的，以使 Stack::create() 能够重新用它

    namespace Stack    // 表示
    {
        const int max_size = 200;

        struct Rep
        {
            char v[max_size];
            int top;
        };

        const int max = 16;    // 最大堆栈数
        Rep stacks[max];       // 预分配的堆栈表示
        bool used[max];        // 如果stacks[i]在使用, 则used[i]为真

        typedef Rep& stack;
    }

    void Stack::push(Stack::stack s, char c) { /* 检查s的上溢并压入c */ }
    char Stack::pop(Stack::stack s) { /* 检查s的下溢并弹出 */ }
    Stack::stack Stack::create()
    {
        // 找一个未使用的Rep, 将它标记为已使用的，将它初始化，并返回它的引用
    }
    void Stack::destroy(Stack::stack s) { /* 标记s为未使用的 */ }

我们在这里做的就是围绕着一个表示类型包装起一组界面函数。所做的结果得到的“堆栈类型”具有怎样的行为，部分在于我们如何定义这些界面函数，部分在于我们如何将Stack的表示展示给它的用户，部分在于这个表示本身的设计情况。

这种做法常常不是最理想的。一个重要问题就是，这里给用户提供了一个“假类型”的表示，它可以因为表示类型不同而出现很大变化---而与此同时，又应该将用户隔离于这一表示之外。例如，如果我们选择采用另外一种更精致的数据结构去表示一个堆栈，那么Stack::stack 的表示类型。

更根本的问题是，通过模块实现的这种用户定义类型，它们所提供的对这种类型的访问，在行为上，并不像内部的类型。它们得到的支持也与内部类型不同，而且实际上更少一些。例如，一个 Stack::Rep 能被使用的期间由 Stack::create() 和 Stack::destroy() 控制，而不是由普遍性的语言规则控制。

代码 (edit by shenjun)：

    namespace Stack        // 界面
    {
        struct Rep;                // 声明
        typedef Rep& stack;

        stack create();
        void destroy(stack s);

        void push(stack s, char c);
        char pop(stack s);
        void show(stack s);
    }

    struct Bad_pop{};
    struct Bad_push{};

    struct Overflow{};

    void f()
    {
        Stack::stack s1 = Stack::create();
        Stack::stack s2 = Stack::create();

        Stack::push(s1, 'c');
        Stack::push(s2, 'k');

        /*if (Stack::pop(s1) != 'c') throw Bad_pop();
        if (Stack::pop(s2) != 'k') throw Bad_pop();*/

        Stack::push(s1, 'a');
        Stack::push(s1, 'b');

        Stack::push(s2, 'e');
        Stack::push(s2, 'f');
        Stack::push(s2, 'k');

        Stack::pop(s2);

        Stack::show(s1);
        Stack::show(s2);

        Stack::destroy(s1);
        Stack::destroy(s2);
    }

    namespace Stack        // 实现
    {
        const int max_size = 200;

        struct Rep        // 定义
        {
            char v[max_size];
            int top;
            int index;    // 保存当前堆栈在数组中的索引值，以便根据该索引值 destroy
        };

        const int max = 16;            // 最大堆栈数
        Rep stacks[max];            // 预分配的堆栈
        bool used[max];                // 如果stack[i]在使用，则used[i]为true
    }

    void Stack::push(Stack::stack s, char c) 
    {
        /* 检查s的上溢并压入c */
        if (s.top == max_size) throw Bad_push();

        s.v[s.top] = c;
        ++s.top;
    }

    char Stack::pop(Stack::stack s)
    {
        /* 检查s的下溢并弹出 */
        if (s.top == 0) throw Bad_pop();
        --s.top;
        return s.v[s.top];
    }

    Stack::stack Stack::create()
    {
        // 找到一个未使用的Rep，将它标记为已使用的，将它初始化，并返回它的引用
        int index = 0;
        while (Stack::used[index] && index < Stack::max)
        {
            index++;
        }

        if (index == Stack::max) throw Overflow();

        Stack::used[index] = true;        // 使用该堆栈，标记为true
        Stack::stacks[index].top = 0;
        Stack::stacks[index].index = index;
        return Stack::stacks[index];
    }

    void Stack::destroy(Stack::stack s)
    {
        // 标记s为未使用的
        Stack::used[s.index] = false;
    }

    void Stack::show(Stack::stack s)
    {
        for (size_t i = 0; i < s.top; i++)
        {
            printf("%c", s.v[i]);
        }
        printf("\n");
    }

🔚